/*
	插入排序
	空间性能为O(1)
	时间性能为O(n^2),最好的情况的下性能为O(n)

	稳定性:对于相同的元素相对位置不会发生变化,因为是从后往前找
	适用性:直接插入排序算法适用于顺序存储以及链式存储,大部分排序算法仅适用于顺序表
*/
#include <stdio.c>
typedef int ElemType;
void insertSort(ElemType A[], int n)
{
	int i,j;
	for (i = 1; i < n; i++)
	{
		if (A[i] < A[i-1])
		{
			//int k = A[i];
			int k = A[i];
			for (j = i-1; k < A[j]; j--)
			{
				A[j+1] = A[j];
			}

			A[j+1] = k;
		}
	}
}

/*
	折半插入排序
	插入排序是边向后移动边插入,折半插入将两个步骤分离
	先用二分查找找出待插位置然后

	时间复杂度和空间复杂度和插入排序一致,比较的元素少些
*/
void BInsertSort(ElemType A[], int n)
{
	int i,j,low,high,mid;

	for (i = 1; i <= n; i++)
	{
		int k = A[i];//存储待插的元素
		low = 0;
		high = i - 1;
		//查找要插入的位置
		while (low <= high)
		{
			mid = (low + high)/2;

			if (k > A[mid])
				low = mid + 1;
			else
				high = mid -1;
		}

		//将temp插入到A[low]的位置
		for (int j = i; j > low; j--)
		{
			A[j] = A[j - 1];
		}

		A[low] = k;
	}
}

/*
	希尔排序:

*/
void shellSort(ElemType A[], int n)
{
	for (int dk = n/2; dk >= 1; dk = dk/2)
	{
		for (int i = dk; i <= n; i++)
		{
			if (A[i] < A[i - dk])
			{
				int k = A[i];

				for (j = i - dk; j>0 && k<A[j]; j = j - dk)
				{
					A[j+dk] = A[j];
				}

				A[j+dk] = k;
			}//if
		}
	}
}

/*
	冒泡排序
*/
void BubbleSort(ElemType A[], int n)
{
	//int i = 0,j = 1;

	for (int i = 0; i < n; i++)
	{
		int tag = 0;//表示本趟是否发生交换的标志

		for (j = n - 1; j > i; j--)
		{
			if (A[j-1] > A[j])
			{
				swap(A[j-1],A[j]);
				tag = 1;
			}
		}

		if (tag == 0)
			return;

	}
}

/*
	快排非递归方法
*/
void quickSort(ElemType A[], int left, int right)
{
	SqStack s;
	push(s,right);
	push(s,left);

	while (!empty(s))
	{
		int begin;
		pop(s,begin);

		int end;
		pop(s,end);
		
		int div = PartSort(A,begin,end);

		if (begin < div - 1)
		{
			push(s,div-1);
			push(s,begin);
		}

		if (end >div + 1)
		{
			push(s,end);
			push(s,div+1);
		}
	}
}